package main

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func max(x, y int) int {
	if x < y {
		return y
	}
	return x
}

func trap(height []int) int {
	if len(height) <= 1 {
		return 0
	}
	leftMax := make([]int, len(height))  // leftMax[i] 是 i 左侧最高值
	rightMax := make([]int, len(height)) // rightMax[i] 是 i 右侧最高值
	for i := range height {
		if i == 0 {
			continue
		}
		leftMax[i] = max(height[i-1], leftMax[i-1])
	}
	for i := len(height) - 2; i >= 0; i-- {
		rightMax[i] = max(rightMax[i+1], height[i+1])
	}
	result := 0
	for i, h := range height {
		m := min(leftMax[i], rightMax[i])
		if m > h {
			result += m - h
		}
	}
	return result
}

func main() {
	println(trap([]int{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}))
	println(trap([]int{4, 2, 0, 3, 2, 5}))
	println(trap([]int{1}))
	println(trap([]int{1, 0}))
}
